<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>The Best Case</title>
<link rel="stylesheet" href="../../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../../index.html" title="Boost.Sort">
<link rel="up" href="../pdqsort.html" title="2.2.- pdqsort">
<link rel="prev" href="pdqsort_benchmark.html" title="Benchmark">
<link rel="next" href="pdqsort_avg.html" title="The Average Case">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="pdqsort_benchmark.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../pdqsort.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="pdqsort_avg.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="sort.single_thread.pdqsort.pdqsort_best"></a><a class="link" href="pdqsort_best.html" title="The Best Case">The Best Case</a>
</h4></div></div></div>
<p>
          <code class="literal"><code class="computeroutput">pdqsort</code></code>
          is designed to run in linear time for a couple of best-case patterns. Linear
          time is achieved for inputs that are in strictly ascending or descending
          order, only contain equal elements, or are strictly in ascending order
          followed by one out-of-place element. There are two seperate mechanisms
          at play to achieve this.
        </p>
<p>
          For equal elements a smart partitioning scheme is used that always puts
          equal elements in the partition containing elements greater than the pivot.
          When a new pivot is chosen it's compared to the greatest element in the
          partition before it. If they compare equal we can derive that there are
          no elements smaller than the chosen pivot. When this happens we switch
          strategy for this partition, and filter out all elements equal to the pivot.
        </p>
<p>
          To get linear time for the other patterns we check after every partition
          if any swaps were made. If no swaps were made and the partition was decently
          balanced we will optimistically attempt to use insertion sort. This insertion
          sort aborts if more than a constant amount of moves are required to sort.
        </p>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2014-2017 Steven
      Ross, Francisco Tapia, Orson Peters<p>
        Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
        Software License, Version 1.0</a>.
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="pdqsort_benchmark.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../pdqsort.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="pdqsort_avg.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
